//import java.util.ArrayList;
//import java.util.List;
//
///**
// * Created by cc
// * Description:
// * User: CZH
// * Date: 2022-10-26
// * Time: 14:26
// */
//class Node{
//    public char val;
//    public Node left;
//    public Node right;
//
//    public Node(char val) {
//        this.val = val;
//    }
//}
//
//public class TestBinaryTree {
//
//    //笨方法创建二叉树
//    public Node createTree(){
//        Node A = new Node('A');
//        Node B = new Node('B');
//        Node C = new Node('C');
//        Node D = new Node('D');
//        Node E = new Node('E');
//        Node F = new Node('F');
//        Node G = new Node('G');
//        Node H = new Node('H');
//
//        A.left = B;
//        A.right = C;
//        B.left = D;
//        B.right = E;
//        C.left = F;
//        C.right = G;
//        E.right = H;
//
//        return A;
//    }
//
//    //前序遍历. 根左右
//    void preOrderTraversal(Node root) {
//        if (root == null) {
//            return;
//        }
//        System.out.print(root.val + " ");
//        preOrderTraversal(root.left);
//        preOrderTraversal(root.right);
//    }
//
//    //中序遍历. 左根右
//    void inOrderTraversal(Node root) {
//        if (root == null) {
//            return;
//        }
//        inOrderTraversal(root.left);
//        System.out.print(root.val + " ");
//        inOrderTraversal(root.right);
//    }
//
//    //后序遍历. 左右根
//    void postOrderTraversal(Node root) {
//        if (root == null) {
//            return;
//        }
//        postOrderTraversal(root.left);
//        postOrderTraversal(root.right);
//        System.out.print(root.val + " ");
//    }
//
//    //前序递归. 使用list来存储数据(子问题思路)
//    public List<Character> preorderTraversal1(Node root) {
//        List<Character> list = new ArrayList<>();
//        if (root == null) {
//            return list;
//        }
//        list.add(root.val);
//        List<Character> leftTree = preorderTraversal1(root.left);
//        list.addAll(leftTree);
//
//        List<Character> rightTree = preorderTraversal1(root.right);
//        list.addAll(rightTree);
//
//        return list;
//    }
//
//    //前序递归. 使用list来存储数据(遍历思路)
//    public List<Character> preorderTraversal2(Node root) {
//        List<Character> list = new ArrayList<>();
//        if (root == null) {
//            return list;
//        }
//        list.add(root.val);
//        preorderTraversal2(root.left);
//        preorderTraversal2(root.right);
//        return list;
//    }
//
//    //遍历思路-求结点个数
//    static int size = 0;
//    void getSize1(Node root) {
//        if (root == null) {
//            return;
//        }
//        size++;
//        getSize1(root.left);
//        getSize1(root.right);
//    }
//
//    //子问题思路-求结点个数
//    int getSize2(Node root) {
//        if (root == null) {
//            return 0;
//        }
//        return getSize2(root.left) + getSize2(root.right) + 1;
//    }
//
//    //遍历思路-求叶子结点个数
//    static int leafSize = 0;
//    void getLeafSize1(Node root) {
//        if (root == null) {
//            return;
//        }
//        if (root.left == null && root.right == null) {
//            leafSize++;
//            return;
//        }
//        getLeafSize1(root.left);
//        getLeafSize1(root.right);
//    }
//
//    //子问题思路-求叶子结点个数
//    int getLeafSize2(Node root) {
//        if (root == null) {
//            return 0;
//        }
//        if (root.left == null && root.right == null) {
//            return 1;
//        }
//        return getLeafSize2(root.left) + getLeafSize2(root.right);
//    }
//
//    //遍历思路-求第k层的结点个数
//    static int levelSize = 0;
//    int getKLevelSize1(Node root, int k) {
//        if (root == null) {
//            return 0;
//        }
//        if (k == 1) {
//            levelSize++;
//        }
//        getKLevelSize1(root.left,k-1);
//        getKLevelSize1(root.right,k-1);
//        return levelSize;
//    }
//
//    //子问题思路-求第k层的结点个数
//    int getKLevelSize2(Node root, int k) {
//        if (root == null) {
//            return 0;
//        }
//        if (k == 1) {
//            return 1;
//        }
//        return getKLevelSize2(root.left,k-1)
//                + getKLevelSize2(root.right,k-1);
//    }
//
//    //获取二叉树的高度
//    int getHeight(Node root) {
//        if (root == null) {
//            return 0;
//        }
//        int leftHeight = getHeight(root.left);
//        int rightHeight = getHeight(root.right);
//        //递归的时候，疯狂+
//        return Math.max(leftHeight,rightHeight) + 1;
//    }
//
//    //获取二叉树中的val值
//    Node findVal(Node root, char val) {
//        if (root == null) {
//            return null;
//        }
//        //找中间
//        if (root.val == val) {
//            return root;
//        }
//        //找左子树
//        Node ret = findVal(root.left, val);
//        if (ret != null) {
//            return ret;
//        }
//        //找右子树
//        ret = findVal(root.right, val);
//        return ret;
//    }
//}
